{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Put Marbles in Bags"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: putMarbles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将珠子放入背包中"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有&nbsp;<code>k</code>&nbsp;个背包。给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>weights</code>&nbsp;，其中&nbsp;<code>weights[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个珠子的重量。同时给你整数 <code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你按照如下规则将所有的珠子放进&nbsp;<code>k</code>&nbsp;个背包。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>没有背包是空的。</li>\n",
    "\t<li>如果第&nbsp;<code>i</code>&nbsp;个珠子和第&nbsp;<code>j</code>&nbsp;个珠子在同一个背包里，那么下标在&nbsp;<code>i</code>&nbsp;到&nbsp;<code>j</code>&nbsp;之间的所有珠子都必须在这同一个背包中。</li>\n",
    "\t<li>如果一个背包有下标从&nbsp;<code>i</code>&nbsp;到&nbsp;<code>j</code>&nbsp;的所有珠子，那么这个背包的价格是&nbsp;<code>weights[i] + weights[j]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一个珠子分配方案的 <strong>分数</strong>&nbsp;是所有 <code>k</code>&nbsp;个背包的价格之和。</p>\n",
    "\n",
    "<p>请你返回所有分配方案中，<strong>最大分数</strong>&nbsp;与 <strong>最小分数</strong>&nbsp;的 <strong>差值</strong>&nbsp;为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>weights = [1,3,5,1], k = 2\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "分配方案 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6 。\n",
    "分配方案 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10 。\n",
    "所以差值为 10 - 6 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>weights = [1, 3], k = 2\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>唯一的分配方案为 [1],[3] 。\n",
    "最大最小得分相等，所以返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= weights.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= weights[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [put-marbles-in-bags](https://leetcode.cn/problems/put-marbles-in-bags/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [put-marbles-in-bags](https://leetcode.cn/problems/put-marbles-in-bags/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,1]\\n2', '[1,3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        values = sorted([a + b for a, b in pairwise(weights)])\n",
    "        return sum(values[-(k - 1): ]) - sum(values[: k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        avg = [(weights[i]+weights[i+1]) for i in range(n-1)]\n",
    "        avg.sort()\n",
    "        return sum(avg[-(k-1):])-sum(avg[:(k-1)]) if k>1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        values = sorted([a + b for a, b in pairwise(weights)])\n",
    "        return sum(values[-(k - 1):]) - sum(values[: k - 1])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1: return 0\n",
    "        b = [w1 + w2 for w1, w2 in zip(weights, weights[1:])]\n",
    "        b.sort()\n",
    "        return sum(b[-k+1:]) - sum(b[:k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        n = len(wt)\n",
    "        a = [wt[i] + wt[i - 1] for i in range(1, n)]\n",
    "        a.sort()\n",
    "        return sum(a[-(k - 1):]) - sum(a[:(k - 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        if n == k:\n",
    "            return 0\n",
    "\n",
    "        h = []\n",
    "        for i in range(1, n):\n",
    "            h.append(weights[i] + weights[i-1])\n",
    "        h.sort()\n",
    "\n",
    "        # print(h)\n",
    "\n",
    "        res = 0\n",
    "        left, right = 0, len(h) - 1\n",
    "        while k > 1:\n",
    "            res += h[right] - h[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "            k -= 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        nums = []\n",
    "        n = len(weights)\n",
    "        for i in range(1, n):\n",
    "            nums.append(weights[i] + weights[i - 1])\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1, n - k, -1):\n",
    "            ans += nums[i] \n",
    "        for i in range(k - 1):\n",
    "            ans -= nums[i] \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        w = []\n",
    "        for i in range(n-1):\n",
    "            w.append(weights[i]+weights[i+1])\n",
    "        w.sort()\n",
    "        res = 0\n",
    "        for i in range(k-1):\n",
    "            res += (w[n-2-i] - w[i])\n",
    "        return res\n",
    "        '''\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        n = len(weights)\n",
    "        dp_max = [[-1]*k for _ in range(2)]\n",
    "        dp_min = [[1e14]*k for _ in range(2)]\n",
    "        for i in range(1,n):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            dp_max[i__][0] = weights[0]+weights[i-1]\n",
    "            dp_min[i__][0] = weights[0]+weights[i-1]\n",
    "            for j in range(max(1,k-n+i),min(k,i+1)):\n",
    "                dp_max[i_][j] = max(dp_max[i__][j-1] + 2*weights[i], dp_max[i__][j] - weights[i-1] + weights[i])\n",
    "                dp_min[i_][j] = min(dp_min[i__][j-1] + 2*weights[i], dp_min[i__][j] - weights[i-1] + weights[i])\n",
    "        return dp_max[(n-1)%2][-1] - dp_min[(n-1)%2][-1]\n",
    "        '''\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        tmp = [weights[i]+weights[i+1] for i in range(len(weights)-1)]\n",
    "        tmp.sort()\n",
    "        return sum(tmp[len(tmp)-k+1:]) - sum(tmp[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: list[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums = sorted([a + b for a, b in pairwise(weights)])\n",
    "        return sum(nums[-(k-1):]) - sum(nums[:k-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        values = sorted([a + b for a, b in pairwise(weights)])\n",
    "        return sum(values[-(k - 1):]) - sum(values[: k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        if k == 1 or k == n:\n",
    "            return 0\n",
    "        w = []\n",
    "        for i in range(n-1):\n",
    "            w.append(weights[i]+weights[i+1])\n",
    "        w.sort()\n",
    "        res = 0\n",
    "        for i in range(min(k-1,n-k)):\n",
    "            res += (w[n-2-i] - w[i])\n",
    "        return res\n",
    "        '''\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        n = len(weights)\n",
    "        dp_max = [[-1]*k for _ in range(2)]\n",
    "        dp_min = [[1e14]*k for _ in range(2)]\n",
    "        for i in range(1,n):\n",
    "            i_ = i%2\n",
    "            i__ = (i-1)%2\n",
    "            dp_max[i__][0] = weights[0]+weights[i-1]\n",
    "            dp_min[i__][0] = weights[0]+weights[i-1]\n",
    "            for j in range(max(1,k-n+i),min(k,i+1)):\n",
    "                dp_max[i_][j] = max(dp_max[i__][j-1] + 2*weights[i], dp_max[i__][j] - weights[i-1] + weights[i])\n",
    "                dp_min[i_][j] = min(dp_min[i__][j-1] + 2*weights[i], dp_min[i__][j] - weights[i-1] + weights[i])\n",
    "        return dp_max[(n-1)%2][-1] - dp_min[(n-1)%2][-1]\n",
    "        '''\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n=len(weights)\n",
    "        bag=[0]*(n-1)\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            bag[i]=weights[i]+weights[i+1]\n",
    "\n",
    "        bag.sort()\n",
    "        print(bag,sum(bag[n-k-1:]),sum(bag[:k]))\n",
    "        ans=sum(bag[n-k:])-sum(bag[:k-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, w: List[int], k: int) -> int:\n",
    "        n = len(w)\n",
    "        rec = []\n",
    "        for i in range(n - 1):\n",
    "            rec.append(w[i] + w[i + 1])\n",
    "        rec.sort()\n",
    "        ans = 0\n",
    "        for i in range(k - 1):\n",
    "            ans += rec[-(i + 1)] - rec[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        tpSum = []\n",
    "        for i in range(n - 1):\n",
    "            tpSum.append(weights[i] + weights[i + 1])\n",
    "        \n",
    "        tpSum.sort()\n",
    "        topKSum, bottomKSum = 0, 0\n",
    "        for i in range(k - 1):\n",
    "            bottomKSum += tpSum[i]\n",
    "            topKSum += tpSum[len(tpSum) - 1 - i]\n",
    "        \n",
    "        return topKSum - bottomKSum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        for i in range(len(weights) - 1):\n",
    "            weights[i] += weights[i + 1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[len(weights) - k + 1:]) - sum(weights[:k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k==1: return 0\n",
    "        lst = sorted(weights[j]+weights[j-1] for j in range(1,len(weights)))\n",
    "        return sum(lst[1-k:])-sum(lst[:k-1]) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        for i in range(len(weights)-1):\n",
    "            weights[i]+=weights[i+1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[len(weights)-k+1:]) - sum(weights[:k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        # k 2*k个节点 dp[]大小2*k\n",
    "\n",
    "        # w[0],w[-1]\n",
    "        # 对i in len(w) : w[i]+w[i+1] k-1对\n",
    "        #找出数组中间的k-1对值，最大/最小 \n",
    "        if k == 1:\n",
    "            return 0\n",
    "        dp = []\n",
    "        l = len(weights)\n",
    "        for i in range(len(weights)-1):\n",
    "            dp.append(weights[i]+weights[i+1])\n",
    "\n",
    "        dp = sorted(dp,reverse=True)\n",
    "        print(dp)\n",
    "        res1 = sum(dp[:k-1])\n",
    "        res2 = sum(dp[-k+1:])\n",
    "        print(res1,res2)\n",
    "        return res1-res2\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, w: List[int], k: int) -> int:\n",
    "        for i in range(len(w)-1):\n",
    "            w[i] += w[i+1]\n",
    "        w.pop()\n",
    "        w.sort()\n",
    "        return sum(w[len(w)-k+1:]) - sum(w[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        for i in range(len(weights) - 1):\n",
    "            weights[i] += weights[i + 1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[len(weights) - k + 1:]) - sum(weights[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(n - 1):\n",
    "            weights[i] += weights[i + 1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[(n-k):])-sum(weights[:(k-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        for i in range(n-1):\n",
    "            weights[i] += weights[i+1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[n-k:]) - sum(weights[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        for i in range(len(weights)-1):\n",
    "            weights[i]+=weights[i+1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[len(weights)-k+1:]) - sum(weights[:k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        if n == k:\n",
    "            return 0\n",
    "        partition = []\n",
    "        for i in range(n-1):\n",
    "            partition.append(weights[i] + weights[i+1])\n",
    "        partition = sorted(partition)\n",
    "        res = 0\n",
    "        for i in range(k-1):\n",
    "            res += partition[n-2-i] - partition[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        #连续子数组\n",
    "        #数组划分成k个\n",
    "        #子数组的两个端点相加是分数\n",
    "        #看上去是DP，但数据范围太大\n",
    "        #分界线往哪里放的问题\n",
    "        #分界线左右两边的数要同时选\n",
    "        #同一个数可能会算两次\n",
    "        #放分界线选相邻两个数，不会影响其他数\n",
    "        #选择是顺序无关的 类似子序列-->能不能排序？ \n",
    "        #k个背包是k-1条分割线 \n",
    "        n=len(weights)\n",
    "        for i in range(n-1):\n",
    "            weights[i]=weights[i]+weights[i+1]\n",
    "        weights.pop()\n",
    "        weights.sort()\n",
    "        return sum(weights[n-k:])-sum(weights[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, w: List[int], k: int) -> int:\n",
    "        n=len(w)\n",
    "        r=[]\n",
    "        for i in range(n-1):\n",
    "            r.append(w[i]+w[i+1])\n",
    "        r.sort()\n",
    "        return sum(r[::-1][:k-1])- sum(r[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        # 计算前缀和\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()  # 丢弃最后一个元素\n",
    "        wt.sort()  # 对前缀和进行排序\n",
    "\n",
    "        # 返回最大和最小分数的差值\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        values = sorted([a + b for a, b in pairwise(weights)])\n",
    "        return sum(values[-(k - 1):]) - sum(values[: k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, wt: List[int], k: int) -> int:\n",
    "        for i in range(len(wt) - 1):\n",
    "            wt[i] += wt[i + 1]\n",
    "        wt.pop()\n",
    "        wt.sort()\n",
    "        return sum(wt[len(wt) - k + 1:]) - sum(wt[:k - 1])\n",
    "\n",
    "# 作者：endlesscheng\n",
    "# 链接：https://leetcode.cn/problems/put-marbles-in-bags/solution/wen-ti-zhuan-hua-pai-xu-tan-xin-by-endle-bx8t/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        n = len(weights)\n",
    "        w = []\n",
    "        for i in range(1, n):\n",
    "            w.append(weights[i] + weights[i-1])\n",
    "        w.sort()\n",
    "        return sum(w[-(k-1):]) - sum(w[:k-1])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        if n == k:\n",
    "            return 0\n",
    "\n",
    "        h = []\n",
    "        for i in range(1, n):\n",
    "            h.append(weights[i] + weights[i-1])\n",
    "        h.sort()\n",
    "\n",
    "        # print(h)\n",
    "        return sum(h[len(h) - k + 1:]) - sum(h[:k - 1])\n",
    "\n",
    "        # res = 0\n",
    "        # left, right = 0, len(h) - 1\n",
    "        # while k >= 1:\n",
    "        #     res += h[right] - h[left]\n",
    "        #     left += 1\n",
    "        #     right -= 1\n",
    "        #     k -= 1\n",
    "\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        n = len(weights)\n",
    "        w_sort = []\n",
    "        for i in range(n-1):\n",
    "            w_sort.append(weights[i] + weights[i+1])\n",
    "\n",
    "        w_sort.sort()\n",
    "        minW = sum(w_sort[:k-1])\n",
    "        maxW = sum(w_sort[-(k-1):])\n",
    "        return maxW - minW\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, w: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        n = len(w)\n",
    "        a = list()\n",
    "        for i in range(n - 1):\n",
    "            a.append(w[i] + w[i + 1])\n",
    "        a.sort()\n",
    "        # print(a)\n",
    "        min_val = sum(a[:k - 1])\n",
    "        max_val = sum(a[-(k - 1):])\n",
    "        # print(min_val, max_val)/\n",
    "        return max_val - min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        sums=[]\n",
    "        if k==1:return 0\n",
    "        for i in range(0,len(weights)-1):\n",
    "            sums.append(weights[i]+weights[i+1])\n",
    "        sums.sort()\n",
    "        return sum(sums[-k+1:])-sum(sums[:k-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        new = []\n",
    "        for i in range(1, n):\n",
    "            new.append(weights[i] + weights[i - 1])\n",
    "        new.sort()\n",
    "        # print(new[len(new) - k + 1 : ])\n",
    "        return sum(new[len(new) - k + 1 : ]) - sum(new[ : k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k==1:\n",
    "            return 0\n",
    "        n=len(weights)\n",
    "        score=[]\n",
    "        for i in range(n-1):\n",
    "            score.append(weights[i]+weights[i+1])\n",
    "        score.sort()\n",
    "        k-=1\n",
    "        return sum(score[-k:])-sum(score[0:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1: return 0\n",
    "        \n",
    "        n = len(weights)\n",
    "        points = [0] * (n - 1)\n",
    "        for i in range(n - 1):\n",
    "            points[i] = weights[i] + weights[i + 1]\n",
    "        points.sort(reverse=True)\n",
    "\n",
    "        max_points = sum(points[:k - 1])\n",
    "        min_points = sum(points[-(k - 1):])\n",
    "        \n",
    "        return max_points - min_points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1: return 0\n",
    "        \n",
    "        n = len(weights)\n",
    "        points = [0] * (n - 1)\n",
    "        for i in range(n - 1):\n",
    "            points[i] = weights[i] + weights[i + 1]\n",
    "        points.sort(reverse=True)\n",
    "\n",
    "        max_points = sum(points[:k - 1])\n",
    "        min_points = sum(points[-(k - 1):])\n",
    "        \n",
    "        return max_points - min_points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        new = []\n",
    "        for i in range(1, n):\n",
    "            new.append(weights[i] + weights[i - 1])\n",
    "        new.sort()\n",
    "        # print(new[len(new) - k + 1 : ])\n",
    "        return sum(new[len(new) - k + 1 : ]) - sum(new[ : k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        scores = []\n",
    "        for i in range(len(weights)-1):\n",
    "            scores.append(weights[i]+weights[i+1])\n",
    "\n",
    "        scores.sort()\n",
    "        n = len(scores)\n",
    "        return sum(scores[n-k+1:n]) - sum(scores[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        ws = []\n",
    "        for i in range(1, len(weights)):\n",
    "            ws.append(weights[i-1]+weights[i])\n",
    "        ws.sort()\n",
    "        return sum(ws[len(ws)-k+1:]) - sum(ws[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        t = []\n",
    "        n = len(weights)\n",
    "        for i in range(n-1):\n",
    "            t.append(weights[i+1] + weights[i])\n",
    "        t.sort()\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return sum(t[n-k:n-1])-sum(t[0:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        '''\n",
    "        区间划分\n",
    "        分成k段区间\n",
    "        先去除首和尾\n",
    "        k=2 找score[i]\n",
    "        k=3 找score[i]+score[j] \n",
    "        同一个重量可以被算两次，所以没有约束\n",
    "        '''\n",
    "        n=len(weights)\n",
    "        score=[0]*(n-1)\n",
    "        for i in range(n-1):\n",
    "            score[i]=weights[i]+weights[i+1]\n",
    "        score.sort()\n",
    "        return sum(score[n-k:])-sum(score[:k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n=len(weights)\n",
    "        bag=[0]*(n-1)\n",
    "        for i in range(n-1):\n",
    "            bag[i]=weights[i]+weights[i+1]\n",
    "\n",
    "        bag.sort()\n",
    "        ans=sum(bag[n-k:])-sum(bag[:k-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        L=[]\n",
    "        for i in range(1,len(weights)):\n",
    "            L.append(weights[i]+weights[i-1])\n",
    "        L.sort(key= lambda x:-x)\n",
    "        c=0\n",
    "        for i in range(k-1):\n",
    "            c+=L[i]-L[-i-1]\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        heap1 = []\n",
    "        heap2 = []\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            e = weights[i]+weights[i-1]\n",
    "            heappush(heap1, e)\n",
    "            heappush(heap2, -e)\n",
    "        for i in range(k-1):\n",
    "            res += heappop(heap1) + heappop(heap2)\n",
    "        return -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        heap = []\n",
    "        heap2 = []\n",
    "        for i in range(n-1):\n",
    "            x = weights[i] + weights[i+1]\n",
    "            heapq.heappush(heap, x)\n",
    "            heapq.heappush(heap2, -x)\n",
    "        ans = 0\n",
    "        for i in range(k-1):\n",
    "            \n",
    "            ans = ans - heapq.heappop(heap) - heapq.heappop(heap2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        qT = []\n",
    "        qH = []\n",
    "        for i in range(len(weights)-1):\n",
    "            heapq.heappush(qT, weights[i]+weights[i+1])\n",
    "            heapq.heappush(qH, -(weights[i]+weights[i+1]))\n",
    "        sumT = 0\n",
    "        sumH = 0\n",
    "        for i in range(k-1):\n",
    "            sumT += heapq.heappop(qT)\n",
    "            sumH += -heapq.heappop(qH)\n",
    "        return sumH-sumT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        qT = []\n",
    "        qH = []\n",
    "        for i in range(len(weights)-1):\n",
    "            heapq.heappush(qT, weights[i]+weights[i+1])\n",
    "            heapq.heappush(qH, -(weights[i]+weights[i+1]))\n",
    "        sumT = 0\n",
    "        sumH = 0\n",
    "        for i in range(k-1):\n",
    "            sumT += heapq.heappop(qT)\n",
    "            sumH += -heapq.heappop(qH)\n",
    "        return sumH-sumT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        w = [a + b for a, b in zip(weights, weights[1:])]\n",
    "        n = len(weights)\n",
    "        seq = sorted(list(range(n - 1)), key=lambda x:w[x])\n",
    "        r = 0\n",
    "        for p in seq[:k - 1]:\n",
    "            r -= weights[p] + weights[p + 1]\n",
    "        for p in seq[n - k:]:\n",
    "            r += weights[p] + weights[p + 1]\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        w = [a + b for a, b in zip(weights, weights[1:])]\n",
    "        seq = sorted(list(range(len(w))), key=lambda x:w[x])\n",
    "        r = 0\n",
    "        for p in seq[:k - 1]:\n",
    "            r -= weights[p] + weights[p + 1]\n",
    "        for p in seq[1 - k:]:\n",
    "            r += weights[p] + weights[p + 1]\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        w = [a + b for a, b in zip(weights, weights[1:])]\n",
    "        seq = sorted(list(range(len(w))), key=lambda x:w[x])\n",
    "        rmin = weights[0] + weights[-1]\n",
    "        for p in seq[:k - 1]:\n",
    "            rmin += weights[p] + weights[p + 1]\n",
    "        rmax = weights[0] + weights[-1]\n",
    "        for p in seq[1 - k:]:\n",
    "            rmax += weights[p] + weights[p + 1]\n",
    "        print(rmax, rmin)\n",
    "        return rmax - rmin\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def putMarbles(self, weights: List[int], k: int) -> int:\n",
    "        n = len(weights)\n",
    "        avg = [(weights[i]+weights[i+1]) for i in range(n-1)]\n",
    "        big = heapq.nlargest(k-1, avg)\n",
    "        small = heapq.nsmallest(k-1, avg)\n",
    "        return sum(big)-sum(small)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
